這題目主要考察字串搜尋的基本技能，並挑戰設計有效率的解法。

題目：

給定兩個字串 haystack 和 needle，我們需要找出 needle 在 haystack 中第一次出現的起始索引。如果 needle 不存在於 haystack 中，則回傳 -1。

範例：

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" 在 "sadbutsad" 的起始索引為 0。

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" 不存在於 "leetcode" 中。

解題思路

直接用 std::string::find() 可以嗎？

class Solution {
public:
    int strStr(string haystack, string needle) {
        size_t found = haystack.find(needle);
        if (found != string::npos)
            return found;
        return -1;
    }
};

但這不適合在面試中這樣做，因為主考官不是想考你怎麼使用 std::string::find()。

這邊直接使用暴力法的實做方式，

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() > haystack.size())
            return -1;

        for (int i = 0; i < haystack.size(); i++) {
            for (int j = 0; j < needle.size(); j++) {
                if (haystack[i+j] != needle[j])
                    break;
                if (j == needle.size()-1)
                    return i;
            }
        }
        return -1;
    }
};

時間複雜度：O(n * m)，n 為 haystack 的長度，m 為 needle 的長度，
空間複雜度：O(1)

參考：
#28. Find the Index of the First Occurrence in a String